1374B - Multiply by 2 divide by 6 - CodeForces Solution

// Date: 2023-01-31 14:22:25
// Problem: B. Multiply by 2, divide by 6
// Contest: Codeforces - Codeforces Round #653 (Div. 3)
// URL: https://codeforces.com/problemset/problem/1374/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// --------By WIDA--------

#include <bits/stdc++.h>
using namespace std;
namespace WIDA {
	using LL = long long;
	using PII = pair<LL, LL>;
	using TII = tuple<LL, LL, LL>;
	#define FOR(i,a,b) for (int i = (int)(a); i <= (int)(b); i ++)
	#define FOR2(i,a,b) for (int i = (int)(a); i <= (int)(b); i += 2)
	#define FORD(i,b,a) for (int i = (int)(a); i >= (int)(b); i --)
	#define ALL(a) a.begin(), a.end()
	#define rALL(a) a.rbegin(), a.rend()
	#define pb push_back
	#define fi first
	#define se second
	#define sz size()
	const LL INF = 0x3f3f3f3f3f3f3f3f;
	template <class... Args> void _(Args... args) {
	    auto _ = [&](auto x) { cout << x << " "; };
	    cout << "--->"; int arr[] = {(_(args), 0)...};
	    cout << "\n";
	}
	template <class T> void _i(T args) {
	    cout << "{";
	    for (auto i : args) cout << i << ", "; cout << "}\n";
	}
	template <class T> void _ii(T args) {
	    cout << "{"; 
	    for (auto [i, j] : args) cout << i << " " << j << ", ";
	    cout << "}\n";
	}
	template <class... Args> void __(Args... args) {
	    auto _ = [&](auto x) { cout << x << " "; };
	    int arr[] = {(_(args), 0)...}; cout << "\n";
	}
	#define int long long // Zmod要关闭
	#define endl "\n" // 交互题要关闭
	const int MOD = 998244353; // 看清楚每道题的 MOD
	const int N = 1e6 + 7; // 二维数组要修改 vector<vector<int> > a(n, vector<int> (m, 0));
}
using namespace WIDA;


bool Solve() {
	int n; cin >> n;
	int cnt = 0, ans = 0;
	while (n % 3 == 0) {
		if (n % 2) ++ ans, n /= 3;
		else n /= 6;
		++ cnt;
	}
	if (n == 1) cout << ans + cnt << endl;
	else cout << -1 << endl;
	return 0;
}
signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int Task = 1;
	cin >> Task;
	for (int i = 1; i <= Task; ++ i) {
		Solve();
//		cout << (Solve() ? "YES" : "NO") << endl;
	}
	
	return 0;
}